1. Technical Field
The present application relates generally to an improved data processing device and method. More specifically, the present application is directed to an apparatus and method for transparent multiple hit correction in associative memories.
2. Description of Related Art
A content addressable memory (CAM) is a type of associative memory having an individual logic circuit associated with each memory cell or CAM entry. The individual logic circuits of each memory cell allow for simultaneously comparing the contents of each memory cell of the CAM in a single memory cycle. Because the entire contents of the CAM memory can be searched in one memory cycle, such memories may perform fast searches. CAM memory is especially useful for cache memory as a lookup table to point to an information location for information stored in conventional RAM (random access memory) memory, for example.
FIG. 1 illustrates an example of a known CAM array 100 comprising multiple memory cells 110. The CAM array 100 may be used for various purposes in which quick searching of multiple entries is desirable. For example, CAM arrays are typically used to provide address translation or address resolution, such as for cache accesses.
The memory cells 110 are arranged as an array having rows 120 and columns 130. The rows 120 of the CAM array 100 may sometimes be referred to as “word lines.” The memory cells 110 in a particular row 120 are connected to one another by a match line 114. The match lines 114 of each row 120 are also connected to a hit logic circuit 140 which receives the output from the rows of memory cells 110 and determines which rows result in a match or “hit.” The memory cells 110 in a particular column 130 are connected to one another by search lines 134. The search lines 134 couple the output of the search drivers 150 to the input of the memory cells 110. An output 142 of the hit logic circuit 140 is connected to the input of a secondary storage table memory 160, which may be a RAM, SRAM, or the like, which receives the outputs from the hit logic circuit 140 and outputs a corresponding data entry. The hit logic circuit 140 may also output a hit/miss signal 144 to indicate whether there was a hit detected or not.
In operation, the match lines 114 are pre-charged to a high state in preparation for a next search cycle. The search drivers 150 input the search data into the CAM array 100 through the search lines 134. This search data may be, for example, an input address for address translation or resolution. If the memory cell 110 does not contain the target data, the memory cell 110 causes its associated match line 114 to discharge to ground. If the contents of a particular cell 110 match the applied data received, along its search line 134, the memory cell 110 will allow its match line 114 to remain high. Thus, if all the memory cells 110 in a row 120 match the search data received on the search lines 134, the match line 114 of that row 130 remains high indicating a match. Otherwise, the match line 114 is discharged to ground indicating a mismatch or miscompare, in at least one of the cells 110 on the match line 114.
Based on the particular row 120 in the array 100 that that indicates a “hit,” a corresponding row in the secondary storage table memory 160 is selected. That is, the data in the secondary storage table memory 160 may be indexed by the stored address table represented by the CAM array 100. The corresponding data in the secondary storage table memory 160 may then be output for use by the computing system in which the CAM array 100 is present. This is referred to as a “match read.” The above operation may then be repeated for the next search cycle.
As noted above, a benefit of a CAM array is its ability to search all entries simultaneously. For example, a CAM array that has 1K entries can be searched in one cycle, while a standard memory (SRAM or DRAM) would typically require 1000 cycles to determine if the desired data is present.
However, one limitation of CAM systems is that, at most, only one word line stored in the device should be matched at a time. Nevertheless, a significant problem with existing CAM devices is that a circuit failure or software error external to the CAM device can cause the occurrence of multiple “hits.” For example, in devices used in certain environments, radiation may cause soft error rate (SER) failures of the CAM device. As one example, alpha particles that are typically filtered out by Earth's atmosphere, may cause SER failures of CAM devices in applications where such filtering is not possible, such as in satellites, space vehicles, and other devices intended for use outside of Earth's atmosphere or at very high altitudes.
If a multiple hit condition exists, multiple word-lines are enabled in the CAM device and erroneous outputs are returned. That is, multiple data entries in the secondary storage table memory 160 are simultaneously accessed causing the resulting data output to be invalid. Even worse, data corruption in the secondary storage table memory 160 may result if the access involves shared read/write bitlines.
Since the cause of a multiple hit is unpredictable, the simplest course of action after detection is to invalidate the entire CAM array 100. However, as the CAM array 100 tries to repopulate with valid entries, the miss rate will temporarily rise and negatively impact performance.
Other solutions involve storing the incoming compare address that caused the multiple hit condition and then issuing an invalidate operation on that address in a subsequent cycle. With such a solution, the addresses are invalidated in a manner where these addresses would not be presented to the CAM array for comparison again after detecting that they result in a multiple hit condition. For example, if an address pattern “A” causes a multiple hit condition in the CAM array, the address pattern “A” is stored in a separate memory entity and compared with incoming address patterns in subsequent cycles. If address pattern “A” is seen again at some point in the future, it would not be presented to the CAM array for comparison since it was established in a previous cycle that this pattern causes a multiple hit condition.
While more precise, this solution can have adverse affects to performance as the CAM array 100 will be offline while performing the invalidate operation on the address pattern. In addition, there is the overhead of detecting a multiple hit failure in the CAM array 100 and reactively issuing an invalidate operation as well as comparing the address patterns for all subsequent cycles.